import java.util.Stack;

public class Leet84 {
    public static void main(String[] args) {
        Leet84 l = new Leet84();
        System.out.println(l.largestRectangleArea(new int[]{5,5,1,7,1,1,5,2,7,6}));
    }
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE,t = 0;
        for (int i = 0; i < heights.length; i++) {
            if (stack.isEmpty()||heights[stack.peek()]<=heights[i])
                stack.push(i);
            else{
                while (!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                    t = stack.pop();
                    max = Math.max(max,(i-t)*heights[t]);
                }
                stack.push(t);
                heights[t] = heights[i];
            }
        }
        if (!stack.isEmpty()){
            int top = heights.length;
            while (!stack.isEmpty()){
                t = stack.pop();
                max = Math.max(max,(top-t+1)*heights[t]);
            }
        }
        return max;
    }
//    public int largestRectangleArea(int[] heights) {
//        int max = 0;
//        int re = 0;
//        for (int height : heights) {
//            max = Math.max(height,max);
//        }
//        int[][][] dp = new int[heights.length][max][heights.length];
//        for (int i = 0; i < heights.length; i++) {
//            if (heights[i]==0)
//                continue;
//            for (int j = 0; j < heights[i]; j++) {
//                for (int k = i; k < heights.length; k++) {
//                    if (heights[k]<j+1)
//                        break;
//                    if (i>0&&dp[i-1][j][k]!=0)
//                        dp[i][j][k] = dp[i-1][j][k]-j-1;
//                    else dp[i][j][k] = (j+1)*(k-i+1);
//                    re = Math.max(re,dp[i][j][k]);
//                }
//            }
//        }
//        return re;
//    }
}
